﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//NC200190 二进制枚举结合贪心 问题在于边界情况没有考虑到 存在越界访问情况
//const int N = 16;
//int a[N][N];
//int col[N];
//int n, m, k;
//int calc(int x)
//{
//	int ret = 0;
//	while (x)
//	{
//		x = x & x - 1;
//		//x-=x&-x; 效果相同 记录x中1的个数
//		ret++;
//	}
//	return ret;
//}
//bool cmp(int& x, int& y)//从大到小排序
//{
//	return x > y;
//}
//int main()
//{
//	cin >> n >> m >> k;
//	for (int i = 0; i < n; i++)
//		for (int j = 0; j < m; j++)
//			cin >> a[i][j];
//	//先二进制枚举行的选法 当行固定后再对列进行贪心选法
//	if (k > m || k > n)k = min(m, n);//避免越界访问 k大于任何一个就都可以全选了//或者直接把col开大一点>225
//	int ret = 0;
//	for (int x = 0; x < (1 << n); x++)
//	{
//		memset(col,0,sizeof col);
//		int cnt = calc(x);//检测当前选法选了几行
//		if (cnt > k)continue;//选法非法
//		int sum = 0;
//		for (int i = 0; i < n; i++)
//		{
//			for (int j = 0; j < m; j++)
//			{
//				if ((x >> i) & 1)//选中了当前行
//					sum += a[i][j];
//				else col[j] += a[i][j];
//			}
//		}
//		sort(col, col + m, cmp);
//		//对列进行贪心算法 选k-cnt列
//		for (int i = 0; i < k - cnt; i++)
//		{
//			sum += col[i];
//		}
//		ret = max(sum, ret);
//	}
//	cout << ret << endl;
//	return 0;
//}

//P1056 简单贪心 但sort用法 以及结构体的使用需要学习
//const int N = 1010;
//struct node 
//{
//	int index;
//	int cnt;
//}row[N],col[N];
////根据cnt从大到小进行排序
//bool cmp1(node& x,node& y)
//{
//	return x.cnt > y.cnt;
//}
////根据index从小到大进行排序
//bool cmp2(node& x, node& y)
//{
//	return x.index < y.index;
//}
//int m, n, k, l, d;
//
//int main()
//{
//	cin >> m >> n >> k >> l >> d;
//	for (int i = 1; i <= m; i++)row[i].index = i;//行
//	for (int i = 1; i <= n; i++)col[i].index = i;//列
//	for (int i = 1; i <= d; i++)
//	{
//		int x, y, p, q; cin >> x >> y >> p >> q;
//		if (x == p) col[min(y, q)].cnt++;//行相等则列相邻 
//		else row[min(x, p)].cnt++;
//	}
//	//将两组数据从大到小进行排序
//	sort(row + 1, row + 1 + m, cmp1);
//	sort(col + 1, col + 1 + n, cmp1);
//
//	//在前指定个数据间 按下标进行排序
//	sort(row + 1, row + 1 + k, cmp2);//前k行
//	sort(col + 1, col + 1 + l, cmp2);//前l列
//
//	for (int i = 1; i <= k; i++)
//		cout << row[i].index << " ";
//	cout << endl;
//	for (int i = 1; i <= l; i++)
//		cout << col[i].index << " ";
//	cout << endl;
//	return 0;
//}
//P1094 简单贪心 
//const int N = 3e4 + 10;
//int a[N];
//int main()
//{
//	int w; cin >> w;
//	int n; cin >> n;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	sort(a + 1, a + 1 + n);
//	int left = 1, right = n;
//	int ret = 0;
//	while (left <= right)
//	{
//		if ((a[left] + a[right]) > w) right--;//大于w 大的单独打包 
//		else  right--, left++;//小于等于w 两个放一块
//		ret++;
//	}
//
//	cout << ret << endl;
//	return 0;
//}
// 
//P1115 最大字段和 简单贪心
//const int N = 2e5 + 10;
//int a[N];
//int n;
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	long long int ret = -1e6, sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		sum += a[i];
//		ret = max(ret, sum);
//		if (sum < 0)sum = 0;//贪心思想 只保留大于0的sum 
//	}
//	cout << ret << endl;
//	return 0;
//}

//sum = ∣a[i] − x∣ = 这样⼀个式⼦：i = 1∑n∣a[1] − x∣ + ∣a[2] − x∣ + ... + ∣a[n] − x∣
//• 当 x 取到 n 个数的中位数时，和最⼩；
//• 最⼩和为：(a[n] − a[1]) + (a[n − 1] − a[2]) + ... + (a[n + 1 − n / 2] − a[n / 2]) 
//贪心算法：策略与证明 广集策略
//const int N = 1e5 + 10;
//int a[N];
//int n;
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	sort(a + 1, a + 1 + n);
//	int mid = (1 + n + 1) / 2;
//	int ret = 0;
//	for (int i = 1; i <= n; i++)
//		ret += abs(a[i] - a[mid]);//原理|a-x|+|b-x|>=|a-b| 把仓库建在中间即可
//	cout << ret << endl;
//	return 0;
//}

//P2678 二分答案题 归纳能力 是否能找到题目中的规律来使用
//关键词最短距离 尽可能长
//const int N = 5e4 + 10;
//typedef long long int LL;
//LL a[N];
//LL l, n, m;
//LL calc(LL x)//模拟跳跃
//{
//	LL ret = 0;
//	for (int i = 0; i <= n; i++)
//	{
//		int j = i + 1;
//		while (j <= n && a[j] - a[i] < x) j++;
//		ret += j - i - 1;
//		i = j - 1;
//	}
//	return ret;
//}
//LL check(LL x)//返回当跳跃距离为x时 需要移除的石头数量
//{//存在bug 有特殊情况无法识别 不确定是什么问题
//	LL p1 = 0, p2 = 1;//用两个指针模拟跳跃过程
//	LL ret = 0;
//	while(p2<=n)
//	{
//		if (a[p2] - a[p1] < x)p2++;
//		else
//		{
//			ret += p2 - p1 - 1;
//			p1 = p2; p2++;
//		}
//	}
//	if(p1!=n)//说明最后一步没跳 
//		ret += p2 - p1 - 2;//最后一步 强制跳跃
//	return ret;
//}
//int main()
//{
//	cin >> l >> n >> m;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	a[++n] = l;//跳到终点这一步要考虑
//	//枚举跳跃距离 跳跃距离越大 移走的石头就越多 直到符合条件为止
//	LL left = 1, right = l;//符合结果存在二段性 当跳跃距离够小时 移除石头数目将<=m 此前都>m 所以找到临界点即答案
//	while (left < right)
//	{
//		LL mid = (left + right + 1) / 2;
//		if (calc(mid) <= m)left = mid;
//		else right = mid - 1;
//	}
//	cout << left << endl;
//	return 0;
//}
//P1873 思路同上题 枚举长度分为两段 一段符合条件 找到符合条件中的最大值
//第一次提交报错原因为数值过大 下次不确定情况直接用LL存数据
//typedef long long int LL;
//const int N = 1e6 + 10;
//int a[N];
//int n, maxhigh=0;
//LL m;
//LL calc(int x)
//{
//	LL ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		if (a[i] > x)ret += a[i] - x;
//	}
//	return ret;
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)cin >> a[i], maxhigh = max(maxhigh, a[i]);
//	//刚好的高度 使得其能得到m米木材 即calc(h)>=m 满足二段性 目标在于找到h
//	//从最高处往下枚举 第一个满足条件的高度就是所需要的高度 
//	int left = 0, right = maxhigh;
//	while (left < right)//找到满足条件的右边界点
//	{
//		int mid = (left + right + 1) / 2;
//		if (calc(mid) >= m) left = mid;
//		else right = mid - 1;
//	}
//	cout << left << endl;
//	return 0;
//}
//P2440 二分答案模板题 二分+判断
//const int N = 1e5 + 10;
//int a[N];
//int n, k, maxlen=0;
//int calc(int x)
//{
//	int ret = 0;
//	for (int i = 1; i <= n; i++)ret += a[i] / x;
//	return ret;
//}
//int main()
//{
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++)cin >> a[i], maxlen = max(maxlen, a[i]);
//	//截取长度从后往前枚举 第一次满足条件时 即为最大的长度 每次都需要遍历 时间复杂度为n*n
//	//当截取长度变短时 获得段数即增加 故所找点满足二段性 使用二分答案 时间复杂度为logn*n
//	int left = 1, right = maxlen;
//	while (left < right)
//	{
//		int mid = (left + right + 1) / 2;//其处在段落最右边
//		if (calc(mid) >= k)left = mid;
//		else right = mid - 1;
//	}
//	if (left == 1 && calc(1) < k)cout << "0" << endl;
//	else cout << left << endl;
//	return 0;
//}
//P1678 二分查找的应用 也可以用set结合其内部函数来写
//const int N = 1e5 + 10;
//int a[N];
//int m, n;
//调用库函数
//int binary_find(int x)
//{
//	//在数组a中 找到距离x最近的两个数
//	auto r = *(lower_bound(a + 1, a + 1 + m, x));//大于等于x的数
//	auto l = *(lower_bound(a + 1, a + 1 + m, x)-1);//找大于等于x的数 迭代器-1 即小于x的最大数
//	return min(abs(l - x), abs(r - x));
//}
//根据二段性使用模板
//int binary_find(int x)
//{
//	int left = 1, right = m;
//	while (left < right)//找到大于等于x的数的下标
//	{
//		int mid = (left + right) / 2;
//		if (a[mid] >= x) right = mid;
//		else left = mid + 1;
//	}
//	return min(abs((a[left - 1] - x)), abs((a[left] - x)));
//}
//int main()
//{
//	cin >> m >> n;
//	a[0] = -1e7;//左边加个护法 确保在越界访问时不影响结果
//	for (int i = 1; i <= m; i++)cin >> a[i];
//	sort(a + 1, a + 1 + m);
//	long long int ret = 0;//1e6*1e5>1e9
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		ret += binary_find(x);
//	}
//	cout << ret << endl;
//	return 0;
//}